from typing import *


class Solution:
    def findSubtreeSizes(self, parent: List[int], s: str) -> List[int]:

        def f(parent: List[int]):
            nexts = DefaultDict(list)
            for i, v in enumerate(parent):
                nexts[v].append(i)
            return nexts

        def z(c):
            return ord(c) - ord("a")

        nexts = f(parent)

        def g(cur, np):
            backup = np[z(s[cur])]
            if backup is not None:
                parent[cur] = backup
            np[z(s[cur])] = cur
            for next in nexts[cur]:
                g(next, np)

            np[z(s[cur])] = backup

        g(0, [None] * 26)
        nexts = f(parent)
        ans = [0] * len(s)

        def count(node):
            tot = 1
            for next in nexts[node]:
                tot += count(next)
            ans[node] = tot
            return tot

        count(0)
        return ans
